package Demo53;

import java.util.Stack;

class Solution {
    /**
     * 链表
     * 两数相加
     * https://leetcode.cn/problems/add-two-numbers/submissions/553486591/
     */
    public ListNode addTwoNumbers1(ListNode l1, ListNode l2) {
        ListNode newHead = new ListNode();
        ListNode cur = newHead;
        int tmp = 0;
        while(l1 != null || l2 != null || tmp != 0) {
            // 求和
            if(l1 != null) {
                tmp += l1.val;
                l1 = l1.next;
            }
            if(l2 != null) {
                tmp += l2.val;
                l2 = l2.next;
            }
            // 创建新节点,接入返回链表
            cur.next = new ListNode(tmp % 10);
            cur = cur.next;
            tmp /= 10;
        }
        return newHead.next;
    }
    /**
     * 链表
     * 两数相加 ||
     * https://leetcode.cn/problems/add-two-numbers-ii/
     */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 创建两个栈
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        // 将链表的值放入栈
        while(l1 != null) {
            stack1.push(l1.val);
            l1 = l1.next;
        }
        while(l2 != null) {
            stack2.push(l2.val);
            l2 = l2.next;
        }
        // 创建虚拟头结点
        ListNode newHead = new ListNode();
        // 创建进位辅助变量
        int tmp = 0;
        while(!stack1.isEmpty() || !stack2.isEmpty() || tmp != 0) {
            if(!stack1.isEmpty()) {
                tmp += stack1.pop();
            }
            if(!stack2.isEmpty()) {
                tmp += stack2.pop();
            }
            if(newHead.next == null) {
                // 如果newHead的下一个节点是null,就直接插入
                newHead.next = new ListNode(tmp % 10);
            }else {
                // 使用头插法
                ListNode node = new ListNode(tmp % 10);
                node.next = newHead.next;
                newHead.next = node;
            }
            tmp /= 10;
        }
        return newHead.next;
    }
}